#ifndef SQA_H_
#define SQA_H_

#include "queue.hpp"
#include "stack.hpp"
#include <climits>
#include <cstddef>


namespace lxj
{
// 用栈实现队列
template<size_t Size = 0>
struct Stack2Queue {
    static_assert(Size <= 4096, "容量最大为4096");
    lxj::Stack<int, Size> input, output;

    int front()
    {
        static_assert(Size > 0, "请设置容量");
        if (output.size() != 0) {
            return output.top();
        }
        while (input.size() != 0) {
            output.push(input.top());
            input.pop();
        }
        return output.size() == 0 ? INT_MIN : output.top();
    }

    int back() const
    {
        static_assert(Size > 0, "请设置容量");
        if (input.size() != 0) return input.top();
        decltype(output) s      = output;
        int              result = INT_MIN;
        while (s.size() != 0) {
            result = s.top();
            s.pop();
        }
        return result;
    }

    int size() const { return input.size() + output.size(); }

    bool pop()
    {
        static_assert(Size > 0, "请设置容量");
        if (output.size() != 0) {
            output.pop();
            return true;
        }
        while (input.size() != 0) {
            output.push(input.top());
            input.pop();
        }
        if (output.size() != 0) {
            output.pop();
            return true;
        }

        return false;
    }

    bool push(int value)
    {
        static_assert(Size > 0, "请设置容量");

        if (output.size() == 0) {
            while (input.size() != 0) {
                output.push(input.top());
                input.pop();
            }
        }
        if (size() < Size) {
            input.push(value);
            return true;
        }
        return false;
    }
};

// 用队列实现栈
template<size_t Size = 0>
struct Queue2Stack {
    static_assert(Size <= 4096, "容量最大为4096");
    lxj::Queue<int, Size> _queue;

    int top()
    {
        int  value = INT_MIN;
        auto index = _queue.size() - 1;
        while (index >= 0) {
            int t = _queue.front();
            _queue.pop();
            _queue.push(t);
        }
        if (_queue.size() != 0) {
            value = _queue.front();
            _queue.push(value);
            _queue.pop();
        }
        return value;
    }

    size_t size() const { return _queue.size(); }

    bool pop()
    {
        if (size() == 0) return false;
        int index = _queue.size() - 1;
        while (index-- >= 0) {
            int t = _queue.front();
            _queue.pop();
            _queue.push(t);
        }
        _queue.pop();
        return true;
    }

    bool push(int value)
    {
        if (size() == Size) return false;

        _queue.push(value);
        return true;
    }
};

// 最小栈
template<size_t Size = 0>
struct MinStack {
    lxj::Stack<int, Size> _stack, _min_stack;

    size_t size() const { return _stack.size(); }

    int top() const
    {
        if (_stack.size() == 0) return INT_MIN;
        return _stack.top();
    }

    bool push(int value)
    {
        if (size() >= Size) return false;
        if (size() == 0) {
            _stack.push(value);
            _min_stack.push(value);
            return true;
        }

        _stack.push(value);
        if (value > _min_stack.top()) {
            _min_stack.push(_min_stack.top());
        }
        else {
            _min_stack.push(value);
        }
        return true;
    }

    bool pop()
    {
        if (size() <= 0) return false;
        _stack.pop();
        _min_stack.pop();
        return true;
    }

    int getMin() const
    {
        if (_min_stack.size() == 0) return INT_MIN;
        return _min_stack.top();
    }
};

}   // namespace lxj

#endif